/**
 * 1391. 检查网格中是否存在有效路径
 * https://leetcode-cn.com/problems/check-if-there-is-a-valid-path-in-a-grid/
 */
public class Solutions_1391 {
    public static void main(String[] args) {
//        int[][] grid = {{2, 4, 3}, {6, 5, 2}};  // output: true
//        int[][] grid = {{1, 2, 1}, {1, 2, 1}};  // output: false
//        int[][] grid = {{1, 1, 2}};  // output: false
//        int[][] grid = {{1, 1, 1, 1, 1, 1, 3}};  // output: true
//        int[][] grid = {{2}, {2}, {2}, {2}, {2}, {2}, {6}};  // output: true

//        int[][] grid = {{6, 1, 3}, {4, 1, 5}};  // output: true
        int[][] grid = {{2, 6, 3}, {6, 5, 2}};  // output: false

        boolean result = hasValidPath(grid);
        System.out.println(result);
    }

    private static int row, col;
    // 创建状态数组
    // direction[0]：表示街道类型 1 可以移动到的全部可能
    // direction[0][5] = {{0, 1, 5}：表示街道类型 1 右移可以到达街道类型 5
    private static int[][][] direction;
    public static boolean hasValidPath(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        direction = new int[][][]{
                // 为 1 时，可以向左或向右行动，向左可以到达 1、4、6，向右可以到达 1、3、5
                {{0, -1, 1}, {0, -1, 4}, {0, -1, 6}, {0, 1, 1}, {0, 1, 3}, {0, 1, 5}},
                // 为 2 时，可以向上或向下行动，向上可以到达 2、3、4，向下可以到达 2、5、6
                {{-1, 0, 2}, {-1, 0, 3}, {-1, 0, 4}, {1, 0, 2}, {1, 0, 5}, {1, 0, 6}},
                // 为 3 时，可以向左或向下行动，向左可以到达 1、4、6，向下可以到达 2、5、6
                {{0, -1, 1}, {0, -1, 4}, {0, -1, 6}, {1, 0, 2}, {1, 0, 5}, {1, 0, 6}},
                // 为 4 时，可以向右或向下行动，向右可以到达 1、3、5，向下可以到达 2、5、6
                {{0, 1, 1}, {0, 1, 3}, {0, 1, 5}, {1, 0, 2}, {1, 0, 5}, {1, 0, 6}},
                // 为 5 时，可以向左或向上行动，向左可以到达 1、4、6，向上可以到达 2、3、4
                {{0, -1, 1}, {0, -1, 4}, {0, -1, 6}, {-1, 0, 2}, {-1, 0, 3}, {-1, 0, 4}},
                // 为 6 时，可以向右或向上行动，向右可以到达 1、3、5，向上可以到达 2、3、4
                {{0, 1, 1}, {0, 1, 3}, {0, 1, 5}, {-1, 0, 2}, {-1, 0, 3}, {-1, 0, 4}},
        };
        boolean res = dfs(grid, 0, 0);
        return res;
    }


    public static boolean dfs(int[][] grid, int i, int j) {
        if (i == row - 1 && j == col - 1) {
            return true;
        }
        int cur = grid[i][j];
        // 标记为已访问
        grid[i][j] = -1;
        // cur 可以到达的几个街道
        int[][] dirs = direction[cur - 1];
        for (int[] dir : dirs) {
            int m = i + dir[0];
            int n = j + dir[1];
            int type = dir[2];

            if (m >= 0 && n >= 0 && m < row && n < col && grid[m][n] == type) {
                // 符合条件，进入下一个街道
                boolean res = dfs(grid, m, n);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }
}
